package leetcode;

import java.util.LinkedList;
import java.util.Queue;

public class SurroundRegions {

	public static void main(String[] args) {
		SurroundRegions object = new SurroundRegions();
		char[][] board = new char[1][80];
		board[0] = "OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO".
				toCharArray();
		object.solve(board);
		for (int j = 0; j < board[0].length; j++) {
			System.out.print(board[0][j] + " ");
		}
	}
	
	
	private static final int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, 1 },
			{ 0, -1 } };

	// 所有在边上以及相连的O不能被变为X，其他所有的O此时一定是被X包围的且不在边上或相邻的
	public void solve(char[][] board) {
		if (board == null || board.length <= 0) {
			return;
		}
		int rows = board.length;
		int columns = board[0].length;
		int[] border = { 0, columns - 1, 0, rows - 1 };
		for (int k = 0; k < 2; k++) {
			for (int i = 0; i < rows; i++) {
				if (board[i][border[k]] == 'O') {
					board[i][border[k]] = 'Y';
					dfs(board, i, border[k]);
				}
			}
		}
		for (int k = 2; k < 4; k++) {
			for (int j = 0; j < columns; j++) {
				if (board[border[k]][j] == 'O') {
					board[border[k]][j] = 'Y';
					dfs(board, border[k], j);
				}
			}
		}

		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < columns; j++) {
				if (board[i][j] == 'O') {
					board[i][j] = 'X';
				}else if (board[i][j] == 'Y') {
					board[i][j] = 'O';
				}
			}
		}
	}

	//dfs会导致栈溢出
	public void dfs(char[][] board, int x, int y) {
		for (int i = 0; i < dir.length; i++) {
			int curX = x + dir[i][0];
			int curY = y + dir[i][1];
			if (curX >= board.length || curX < 0 || curY >= board[0].length
					|| curY < 0) {
				continue;
			}
			if (board[curX][curY] == 'O') {
				board[curX][curY] = 'Y';
				dfs(board, curX, curY);
			}
		}
	}
	
	
	
	// BFS
	class Point {  
	    int x;  
	    int y;  
	    Point(int x,int y) {  
	        this.x = x;  
	        this.y = y;  
	    }  
	}  
	
	// 使用bfs还可以降低时间复杂度，可以参见hdu中的MazeProblem
	public void solveBfs(char[][] board) {
        if (board.length == 0) return;
        
        int rowN = board.length;
        int colN = board[0].length;
        Queue<Point> queue = new LinkedList<Point>();
       
		// get all 'O's on the edge first
		for (int r = 0; r < rowN; r++) {
			if (board[r][0] == 'O') {
				board[r][0] = '+';
				queue.add(new Point(r, 0));
			}
			if (board[r][colN - 1] == 'O') {
				board[r][colN - 1] = '+';
				queue.add(new Point(r, colN - 1));
			}
		}
        
        for (int c = 0; c< colN; c++){
        	if (board[0][c] == 'O') {
        		board[0][c] = '+';
                queue.add(new Point(0, c));
        	}
        	if (board[rowN-1][c] == 'O') {
        		board[rowN-1][c] = '+';
                queue.add(new Point(rowN-1, c));
        	}
        }
        

        //BFS for the 'O's, and mark it as '+'
        while (!queue.isEmpty()){
        	Point p = queue.poll();
        	int row = p.x;
        	int col = p.y;
        	if (row - 1 >= 0 && board[row-1][col] == 'O') {
        		board[row-1][col] = '+'; 
        		queue.add(new Point(row-1, col));
        	}
        	if (row + 1 < rowN && board[row+1][col] == 'O') {
        		board[row+1][col] = '+'; 
        		queue.add(new Point(row+1, col));
        	}
        	if (col - 1 >= 0 && board[row][col - 1] == 'O') {
        		board[row][col-1] = '+'; 
        		queue.add(new Point(row, col-1));
        	}
			if (col + 1 < colN && board[row][col + 1] == 'O') {
				board[row][col + 1] = '+';
				queue.add(new Point(row, col + 1));
			}
        }

        //turn all '+' to 'O', and 'O' to 'X'
		for (int i = 0; i < rowN; i++) {
			for (int j = 0; j < colN; j++) {
				if (board[i][j] == 'O')
					board[i][j] = 'X';
				if (board[i][j] == '+')
					board[i][j] = 'O';
			}
		}
    }
}
